package Leetcode.Stack;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/4/20 17:05
 * @Description:
 * 221021天池-03. 整理书架
 * 通过的用户数76
 * 尝试过的用户数241
 * 用户总通过次数81
 * 用户总提交次数562
 * 题目难度Medium
 * 书架上有若干本书，从左至右的书籍编号记于整型数组 order 中。为保证书籍多样性，管理员想取走一些重复编号的书籍，要求满足以下条件：
 *
 * 剩余书本中相同编号的书本数量均不大于 limit
 * 取走的书籍数量尽可能少
 * 由于存在多种整理方案，请返回剩余书本编号的排列为「最小排列」的方案。
 *
 * 注意：
 *
 * 「最小排列」：若干数组中第一位数字最小的数组；若第一位数字相同，则为第二位数字最小的数组，以此类推。
 * 示例 1：
 *
 * 输入：order = [5,5,6,5], limit = 2
 * 输出：[5,5,6]
 * 解释：order 中出现了 3 次 5 号书：
 * 方案 1：去掉 order[0] 或 order[1]，所得排列为 [5,6,5]；
 * 方案 2：去掉 order[3]，所得排列为 [5,5,6]；
 * 经比较，最终返回排列最小的方案 2：[5,5,6]。
 * 示例 2：
 *
 * 输入：order = [5,5,6,5], limit = 3
 * 输出：[5,5,6,5]
 * 解释：order 中所有相同编号的书本数目均未超过 limit，不需要去除，返回 [5,5,6,5]
 * 示例 3：
 *
 * 输入：order = [3,3,9,8,9,2,8], limit = 1
 * 输出：[3,8,9,2]
 * 解释：列表中 3、8、9 号数字都出现了 2 次，去掉编号相同的书后的排列结果中 [3,8,9,2] 为排列最小的结果。
 * 示例 4：
 *
 * 输入：order = [2,1,2,2,1,3,3,1,3,3], limit = 2
 * 输出：[1,2,2,1,3,3]
 * 提示：
 *
 * 1 <= order.length <= 10^5
 * 1 <= limit <= 10
 * 1 <= order[i] <= 10^6
 *
 *
 * limit不知道怎么弄进去
 */

public class arrangeBookshelf {
    public static void main(String[] args) {
        int[] arr = {2,1,2,2,1,3,3,1,3,3};
        int limit = 2;
        System.out.println(Arrays.toString(arrangeBookshelf(arr, limit)));
    }
    public static int[] arrangeBookshelf2(int[] order, int limit) {
        Stack<Integer> st = new Stack<>();
        int[] has = new int[1000010];
        int[] remain = new int[1000010];
        for (int j : order) {
            remain[j]++;
        }
        for (int num : order) {
            if (has[num] == limit) {
                remain[num]--;
                continue;
            }
            while (!st.isEmpty() && st.peek() > num && has[st.peek()] + remain[st.peek()] > limit) {
                has[st.pop()]--;
            }
            has[num]++;
            remain[num]--;
            st.push(num);
        }
        int[] res = new int[st.size()];
        for(int i = res.length - 1;i >= 0;i--) {
            res[i] = st.pop();
        }
        return res;
    }
    public static int[] arrangeBookshelf(int[] order, int limit) {
        Map<Integer, Integer> count_map = new HashMap<>();
        Map<Integer, Integer> exist_map = new HashMap<>();
        if (limit <= 0) {
            return new int[-1];
        }
        for (int j : order) {
            count_map.put(j, count_map.getOrDefault(j, 0) + 1);
        }

        Stack<Integer> stack = new Stack<>();
        for (int num : order) {
            if (exist_map.getOrDefault(num, 0) == limit) {
                count_map.put(num, count_map.get(num) - 1);
                continue;
            }

            while (!stack.isEmpty()
                    && stack.peek() > num
                    && (exist_map.getOrDefault(stack.peek(), 0)
                    + count_map.get(stack.peek()) > limit)) {
                Integer pop = stack.pop();
                exist_map.put(pop, exist_map.get(pop) - 1);
            }
            exist_map.put(num, exist_map.getOrDefault(num, 0) + 1);
            count_map.put(num, count_map.get(num) - 1);
            stack.push(num);
        }
        int size = stack.size();
        int[] ans = new int[size];
        int i = size-1;
        while (!stack.isEmpty()) {
            ans[i] = stack.pop();
            i--;
        }
        return ans;
    }
    //[1, 2, 2, 1, 3, 3]
    //[1, 1, 3, 3]
}
